#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>

//请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
//typedef int QDataType;
//typedef struct QueueNode
//{
//	QDataType val;
//	struct QueueNode* next;
//}QNode;
//
//typedef struct Queue
//{
//	QNode* phead;
//	QNode* ptail;
//	int size;
//}Queue;
//
//void QueueInit(Queue* pq)
//{
//	assert(pq);
//	pq->phead = pq->ptail = NULL;
//	pq->size = 0;
//}
//
//void QueueDestroy(Queue* pq)
//{
//	assert(pq);
//
//	QNode* cur = pq->phead;
//	while (cur)
//	{
//		QNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//
//	pq->phead = pq->ptail = NULL;
//	pq->size = 0;
//}
//
//void QueuePush(Queue* pq, QDataType x)
//{
//	assert(pq);
//
//	QNode* newnode = (QNode*)malloc(sizeof(QNode));
//	if (newnode == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//
//	newnode->val = x;
//	newnode->next = NULL;
//
//	if (pq->ptail == NULL)
//	{
//		pq->ptail = pq->phead = newnode;
//	}
//	else
//	{
//		pq->ptail->next = newnode;
//		pq->ptail = newnode;
//	}
//
//	pq->size++;
//}
//
//// 17:10
//void QueuePop(Queue* pq)
//{
//	assert(pq);
//	// 
//	assert(pq->phead);
//
//	QNode* del = pq->phead;
//	pq->phead = pq->phead->next;
//	free(del);
//	del = NULL;
//
//	if (pq->phead == NULL)
//		pq->ptail = NULL;
//
//	pq->size--;
//}
//
//QDataType QueueFront(Queue* pq)
//{
//	assert(pq);
//	// 
//	assert(pq->phead);
//
//	return pq->phead->val;
//}
//
//QDataType QueueBack(Queue* pq)
//{
//	assert(pq);
//	// 
//	assert(pq->ptail);
//
//	return pq->ptail->val;
//}
//
//bool QueueEmpty(Queue* pq)
//{
//	assert(pq);
//
//	return pq->phead == NULL;
//}
//
//int QueueSize(Queue* pq)
//{
//	assert(pq);
//
//	return pq->size;
//}
//
//typedef struct {
//	Queue q1;
//	Queue q2;
//} MyStack;
//
//
//MyStack* myStackCreate() {
//	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
//
//	QueueInit(&ps->q1);
//	QueueInit(&ps->q2);
//
//	return ps;
//}
//
//void myStackPush(MyStack* obj, int x) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		QueuePush(&obj->q1, x);
//	}
//	else
//	{
//		QueuePush(&obj->q2, x);
//	}
//}
//
//int myStackPop(MyStack* obj) {
//	Queue* emptyq = &obj->q1;
//	Queue* nonemptyq = &obj->q2;
//	if (!QueueEmpty(&obj->q1))
//	{
//		emptyq = &obj->q2;
//		nonemptyq = &obj->q1;
//	}
//
//	while (QueueSize(nonemptyq) > 1)
//	{
//		QueuePush(emptyq, QueueFront(nonemptyq));
//		QueuePop(nonemptyq);
//	}
//
//	int top = QueueFront(nonemptyq);
//	QueuePop(nonemptyq);
//	return top;
//
//}
//
//int myStackTop(MyStack* obj) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		return QueueBack(&obj->q1);
//	}
//	else
//	{
//		return  QueueBack(&obj->q2);
//	}
//}
//
//bool myStackEmpty(MyStack* obj) {
//	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
//}
//
//void myStackFree(MyStack* obj) {
//	QueueDestroy(&obj->q1);
//	QueueDestroy(&obj->q2);
//
//	free(obj);
//}



//用栈实现队列


//typedef int STDataType;
//
//typedef struct Stack
//{
//	STDataType* a;
//	int top;
//	int capacity;
//}ST;
//
//void StackInit(ST* ps)
//{
//	assert(ps);
//
//	ps->a = NULL;
//	ps->top = 0;
//	ps->capacity = 0;
//}
//void StackPush(ST* ps, STDataType x)
//{
//	assert(ps);
//
//	if (ps->capacity == ps->top)
//	{
//		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
//		if (temp == NULL)
//		{
//			printf("增容失败！程序退出");
//			exit(-1);
//		}
//		//增容成功！
//		ps->capacity = newCapacity;
//		ps->a = temp;
//	}
//
//	ps->a[ps->top++] = x;
//
//}
//void StackPop(ST* ps)
//{
//	assert(ps);
//	assert(ps->top > 0);
//
//	ps->top--;
//}
//
//STDataType StackTop(ST* ps)
//{
//	assert(ps);
//	assert(ps->top > 0);
//	return ps->a[ps->top - 1];
//}
//
//bool StackIsEmpty(ST* ps)
//{
//	assert(ps);
//	return ps->top == 0;
//}
//
//
//
//void StackDestroy(ST* ps)
//{
//	assert(ps);
//
//	free(ps->a);
//	ps->a = NULL;
//	ps->capacity = 0;
//	ps->top = 0;
//
//}
//
//typedef struct {
//	ST pushST;
//	ST popST;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
//
//	StackInit(&q->pushST);
//	StackInit(&q->popST);
//	return q;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//
//	StackPush(&obj->pushST, x);
//}
//
//int myQueuePop(MyQueue* obj) {
//
//
//	if (StackIsEmpty(&obj->popST))
//	{
//
//		while (!StackIsEmpty(&obj->pushST))
//		{
//			StackPush(&obj->popST, StackTop(&obj->pushST));
//			StackPop(&obj->pushST);
//		}
//	}
//
//	int front = StackTop(&obj->popST);
//	StackPop(&obj->popST);
//	return front;
//}
//
//int myQueuePeek(MyQueue* obj) {
//
//	if (StackIsEmpty(&obj->popST))
//	{
//
//		while (!StackIsEmpty(&obj->pushST))
//		{
//			StackPush(&obj->popST, StackTop(&obj->pushST));
//			StackPop(&obj->pushST);
//		}
//	}
//	return StackTop(&obj->popST);
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//	return StackIsEmpty(&obj->pushST) && StackIsEmpty(&obj->popST);
//
//}
//
//void myQueueFree(MyQueue* obj) {
//	StackDestroy(&obj->pushST);
//	StackDestroy(&obj->popST);
//	free(obj);
//}
//
